package com.yww.algorithm.recursion;

/**
 * @author yww
 * @description 杨辉三角
 * @since 2024/1/31 18:12
 */
public class PascalTriangle {
    /**
     * 计算第i行，j列的元素值，未优化
     *
     * @param i 行
     * @param j 列
     * @return int 结果
     **/
    public static int cal01(int i, int j) {
        if (j == 0 || i == j) {
            return 1;
        }
        return cal01(i - 1, j - 1) + cal01(i - 1, j);
    }

    public static void print01(int n) {
        for (int i = 0; i < n; i++) {
            printSpace(n, i);

            for (int j = 0; j < i + 1; j++) {
                System.out.printf("%-4d", cal01(i, j));
            }
            System.out.println();
        }
    }

    private static void printSpace(int n, int i) {
        if (i < n - 1) {
            System.out.printf("%" + 2 * (n - 1 - i) + "s", " ");
        }
    }


    public static int cal02(int[][] triangle, int i, int j) {
        if (triangle[i][j] > 0) {
            return triangle[i][j];
        }
        if (j == 0 || i == j) {
            triangle[i][j] = 1;
            return triangle[i][j];
        }
        triangle[i][j] = cal02(triangle, i - 1, j - 1) + cal02(triangle, i - 1, j);
        return triangle[i][j];
    }

    public static void print02(int n) {
        int[][] triangle = new int[n][];
        for (int i = 0; i < n; i++) {
            printSpace(n, i);
            triangle[i] = new int[i + 1];
            for (int j = 0; j < i + 1; j++) {
                cal02(triangle, i, j);
                System.out.printf("%-4d", triangle[i][j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        print01(5);
        print02(5);
    }
}
